/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        TreeLinkNode *head, *tail;
        head=tail=root;
        while (head!=NULL) {
            if (head->left!=NULL) {
                tail->next=head->left;
                tail=tail->next;
            }
            if (head->right!=NULL) {
                tail->next=head->right;
                tail=tail->next;
            }
            head=head->next;
        }
        TreeLinkNode *split=NULL;
        head=tail=root;
        while (head!=NULL) {
            if (split==NULL)
                if (head->left!=NULL) split=head->left; else
                if (head->right!=NULL) split=head->right;
            if (split!=NULL) {
                if (head->next==split) {
                    TreeLinkNode *tmp=head->next;
                    head->next=NULL;
                    head=tmp;
                    split=NULL;
                } else head=head->next;
            } else head=head->next;
        }
    }
};
